package com.example.bitoperation;

/**
 * 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
 *  给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
 *
 *  示例 1：
 * 输入：x = 1, y = 4
 * 输出：2
 * 解释：
 * 1   (0 0 0 1)
 * 4   (0 1 0 0)
 *        ↑   ↑
 * 上面的箭头指出了对应二进制位不同的位置。
 *
 *  示例 2：
 * 输入：x = 3, y = 1
 * 输出：1
 *
 *  提示：
 *  0 <= x, y <= 231 - 1
 */
public class Leetcode461_HammingDistance {
    public static void main(String[] args) {
        String binStr1 = "00000000000000000000000000001011";
        String binStr2 = "00000000001000000001100000000011";
        System.out.println(new Solution().hammingDistance(Integer.parseInt(binStr1, 2), Integer.parseInt(binStr2, 2)));

    }

    static class Solution {
        /**
         * 位运算
         * 先将两个数字进行 ^ ,得到的结果再去求1的个数（汉明重量 leetcode191）
         * @param x
         * @param y
         * @return
         */
        public int hammingDistance(int x, int y) {
            int tmp = x ^ y; // 将不同位置1
            int count = 0;
            // 然后求1的个数(法一)
            while (tmp != 0) {
//                if ((tmp & 1) == 1) {
//                    count++;
//                }
                count += (tmp & 1); // 等价上面的代码
                tmp >>= 1;
            }

            // 然后求1的个数(法二) n & (n - 1) 所得结果1的个数会比n少一个
//            while (tmp != 0) {
//                count++;
//                tmp = (tmp & tmp - 1);
//            }

            return count;
        }
    }
}
